'''
前缀树，trie树，这个结构的代码需要会背写
'''
class trie_node:
    def __init__(self):
        self.path = 0 #有多少节点穿过
        self.end = 0  #有多少节点结束于这个节点
        self.next = [None] * 26

class trie:
    def __init__(self):
        self.root = trie_node() #头节点永远存在
    def insert(self, word: str):
        if len(word) == 0: return
        node = self.root
        node.path += 1
        index = 0
        for i in word:
            index = ord(i) - ord('a')
            if node.next[index] == None:
                node.next[index] = trie_node()
            node = node.next[index]
            node.path += 1
        node.end += 1
    def delete(self, word: str):
        if self.search(word) != 0:
            node = self.root
            index = 0  
            for i in word:
                index = ord(i) - ord('a')
                node.next[index].path -= 1
                if node.next[index].path == 0:  # 如果其中某个字符path为0，则停止遍历
                    node.next[index] = None
                    return
                node = node.next[index]
            node.end -= 1
    def search(self, word: str) -> int:
        if len(word) == 0: return 0
        node = self.root
        index = 0
        for i in word:
            index = ord(i) - ord('a')
            if node.next[index] == None:
                return 0
            node = node.next[index]
        return node.end
    def prefix_number(self, pre: str) ->int: #以某个字符串开头的前缀个数
        if len(pre) == 0: return 0
        node = self.root
        index = 0  
        for i in pre:    
            index = ord(i) - ord('a')
            if node.next[index] == None:
                return 0
            node = node.next[index]
        return node.path

def main() :
	itrie = trie()
	print(itrie.search("zuo"))
	itrie.insert("zuo")
	print(itrie.search("zuo"))
	itrie.delete("zuo")
	print(itrie.search("zuo"))
	itrie.insert("zuo")
	itrie.insert("zuo")
	itrie.delete("zuo")
	print(itrie.search("zuo"))
	itrie.delete("zuo")
	print(itrie.search("zuo"))
	itrie.insert("zuoa")
	itrie.insert("zuoac")
	itrie.insert("zuoab")
	itrie.insert("zuoad")
	itrie.delete("zuoa")
	print(itrie.search("zuoa"))
	print(itrie.prefix_number("zuo"))

if __name__ == "__main__":
    main()